package com.wfm.niuke;

import org.junit.Test;

/**
 * [岛屿的最大面积]
 * 这题关键就是遍历的时候给面积+1
 * 遇到0或者2或者边界返回0
 * 那遇到1肯定没得直接像上面边界条件一样返回，不然没法递归下去了
 * 所以只能在最终return那里+1
 */
public class MaxAreaOfIsland695 {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1){
                    max = Math.max(dfs(grid,i,j),max);
                }
            }
        }
        return max;
    }
    int dfs(int[][] grid,int i ,int j){
        if(!inArea(grid, i , j)){
            return 0;
        }
        if(grid[i][j]==0){
            return 0;
        }
        if(grid[i][j]==2){
            return 0;
        }
        grid[i][j]=2;
        return 1+dfs(grid,i-1,j)+
                dfs(grid,i+1,j)+
                dfs(grid,i,j-1)+
                dfs(grid,i,j+1);
    }

    private boolean inArea(int[][] grid, int i, int j) {
        if(i<0||i>=grid.length||j<0||j>=grid[0].length) return false;
        else return true;
    }

    @Test
    public void test200() {
        System.out.println(maxAreaOfIsland(new int[][]{
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
        }));
    }
}
